package b;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class _9合并区间模板 {

    public int[][] merge(int[][] intervals) {
        //1、排序
        List<int[]> list = new ArrayList<>();
        for (int i = 0; i < intervals.length; i++) {
            list.add(new int[]{intervals[i][0], intervals[i][1]});
        }
        Collections.sort(list, new Comparator<int[]>() {
            @Override
            public int compare(int[] a, int[] b) {
                if(a[0]!=b[0])return a[0]-b[0];
                return b[1]-a[1];
            }
        });

        //2、初始化第一个
        int l = list.get(0)[0], r = list.get(0)[1];
        List<int[]> resList = new ArrayList<>();
        resList.add(new int[]{l,r});

        //3、从第二个开始遍历
        for (int i = 1; i < list.size(); i++) {
            int thisL = list.get(i)[0],thisR = list.get(i)[1];
            //覆盖,跳过当前cur即可 (14,cur23)
            if(r >= thisR){
                continue;
            }
            //相交
            else if(r >= thisL){
                r = thisR;
                resList.remove(resList.size()-1);
                resList.add(new int[]{l,r});
            }
            //相离
            else if(r < thisL){
                l = thisL;
                r = thisR;
                resList.add(new int[]{l,r});
            }
        }

        //4、List转int[][]
        int n = resList.size();
        int[][] res =new int[n][2];
        for (int i = 0; i < resList.size(); i++) {
            int L = resList.get(i)[0];
            int R = resList.get(i)[1];
            res[i][0] = L;
            res[i][1] = R;
        }
        return res;
    }

}
